By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 36, Issue 4, pp. ix-1230

Please Note: Electronic articles are available well in advance of the printed articles.

Special Issue: Randomness and Complexity
What Article options are available ?   View Cart   

Special Issue on Randomness and Complexity

Oded Goldreich and Madhu Sudan

pp. ix-xi

BibTeX  Abstract FREE Full Text:  PDF

Cryptography in $NC^0$

Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz

pp. 845-888

BibTeX  Abstract Full Text:  PDF

Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan

pp. 889-974

BibTeX  Abstract Full Text:  PDF

Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem

Irit Dinur and Omer Reingold

pp. 975-1024

BibTeX  Abstract Full Text:  PDF

Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique

Subhash Khot

pp. 1025-1071

BibTeX  Abstract Full Text:  PDF

Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed

Ariel Gabizon, Ran Raz, and Ronen Shaltiel

pp. 1072-1094

BibTeX  Abstract Full Text:  PDF

Extracting Randomness Using Few Independent Sources

Boaz Barak, Russell Impagliazzo, and Avi Wigderson

pp. 1095-1118

BibTeX  Abstract Full Text:  PDF

On Worst-Case to Average-Case Reductions for NP Problems

Andrej Bogdanov and Luca Trevisan

pp. 1119-1159

BibTeX  Abstract Full Text:  PDF

An Unconditional Study of Computational Zero Knowledge

Salil P. Vadhan

pp. 1160-1214

BibTeX  Abstract Full Text:  PDF

Derandomizing Homomorphism Testing in General Groups

Amir Shpilka and Avi Wigderson

pp. 1215-1230

BibTeX  Abstract Full Text:  PDF